//lettcode
//https://leetcode.cn/problems/minimum-sideway-jumps/


class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
        int n = obstacles.size();
        vector<vector<int>> f(n, vector<int> (3, INT_MAX-1));
        f[0][1] = 0;
        f[0][0] = 1;
        f[0][2] = 1;
        for(int i=1; i<n; i++){
            int pos = obstacles[i] - 1;
            for(int j=0; j<3; j++){
                if(j == pos) continue;
                f[i][j] = f[i-1][j];
                for(int k = 0; k<3; k++){
                    if(k == pos || k == j) continue;
                    f[i][j] = min(f[i][j], f[i-1][k]+1);
                }
            }
            
        }
        return *min_element(f[n-1].begin(), f[n-1].end());
    }
};